home *** CD-ROM | disk | FTP | other *** search
/ Aminet 40 / Aminet 40 (2000)(Schatztruhe)[!][Dec 2000].iso / Aminet / dev / lang / Python16.lha / Python-1.6 / Lib / Python1.6 / sre_parse.py < prev    next >
Encoding:
Python Source  |  2000-09-02  |  20.7 KB  |  659 lines
  1. #
  2. # Secret Labs' Regular Expression Engine
  3. #
  4. # convert re-style regular expression to sre pattern
  5. #
  6. # Copyright (c) 1998-2000 by Secret Labs AB.  All rights reserved.
  7. #
  8. # See the sre.py file for information on usage and redistribution.
  9. #
  10.  
  11. import string, sys
  12.  
  13. from sre_constants import *
  14.  
  15. MAXREPEAT = 65535
  16.  
  17. # FIXME: the following might change in 2.0 final.  but for now, this
  18. # seems to be the best way to be compatible with 1.5.2
  19. CHARMASK = 0xff
  20.  
  21. SPECIAL_CHARS = ".\\[{()*+?^$|"
  22. REPEAT_CHARS  = "*+?{"
  23.  
  24. DIGITS = tuple("0123456789")
  25.  
  26. OCTDIGITS = tuple("01234567")
  27. HEXDIGITS = tuple("0123456789abcdefABCDEF")
  28.  
  29. WHITESPACE = tuple(" \t\n\r\v\f")
  30.  
  31. ESCAPES = {
  32.     r"\a": (LITERAL, 7),
  33.     r"\b": (LITERAL, 8),
  34.     r"\f": (LITERAL, 12),
  35.     r"\n": (LITERAL, 10),
  36.     r"\r": (LITERAL, 13),
  37.     r"\t": (LITERAL, 9),
  38.     r"\v": (LITERAL, 11),
  39.     r"\\": (LITERAL, ord("\\"))
  40. }
  41.  
  42. CATEGORIES = {
  43.     r"\A": (AT, AT_BEGINNING), # start of string
  44.     r"\b": (AT, AT_BOUNDARY),
  45.     r"\B": (AT, AT_NON_BOUNDARY),
  46.     r"\d": (IN, [(CATEGORY, CATEGORY_DIGIT)]),
  47.     r"\D": (IN, [(CATEGORY, CATEGORY_NOT_DIGIT)]),
  48.     r"\s": (IN, [(CATEGORY, CATEGORY_SPACE)]),
  49.     r"\S": (IN, [(CATEGORY, CATEGORY_NOT_SPACE)]),
  50.     r"\w": (IN, [(CATEGORY, CATEGORY_WORD)]),
  51.     r"\W": (IN, [(CATEGORY, CATEGORY_NOT_WORD)]),
  52.     r"\Z": (AT, AT_END), # end of string
  53. }
  54.  
  55. FLAGS = {
  56.     # standard flags
  57.     "i": SRE_FLAG_IGNORECASE,
  58.     "L": SRE_FLAG_LOCALE,
  59.     "m": SRE_FLAG_MULTILINE,
  60.     "s": SRE_FLAG_DOTALL,
  61.     "x": SRE_FLAG_VERBOSE,
  62.     # extensions
  63.     "t": SRE_FLAG_TEMPLATE,
  64.     "u": SRE_FLAG_UNICODE,
  65. }
  66.  
  67. class Pattern:
  68.     # master pattern object.  keeps track of global attributes
  69.     def __init__(self):
  70.         self.flags = 0
  71.         self.groups = 1
  72.         self.groupdict = {}
  73.     def getgroup(self, name=None):
  74.         gid = self.groups
  75.         self.groups = gid + 1
  76.         if name:
  77.             self.groupdict[name] = gid
  78.         return gid
  79.  
  80. class SubPattern:
  81.     # a subpattern, in intermediate form
  82.     def __init__(self, pattern, data=None):
  83.         self.pattern = pattern
  84.         if not data:
  85.             data = []
  86.         self.data = data
  87.         self.width = None
  88.     def dump(self, level=0):
  89.         nl = 1
  90.         for op, av in self.data:
  91.             print level*"  " + op,; nl = 0
  92.             if op == "in":
  93.                 # member sublanguage
  94.                 print; nl = 1
  95.                 for op, a in av:
  96.                     print (level+1)*"  " + op, a
  97.             elif op == "branch":
  98.                 print; nl = 1
  99.                 i = 0
  100.                 for a in av[1]:
  101.                     if i > 0:
  102.                         print level*"  " + "or"
  103.                     a.dump(level+1); nl = 1
  104.                     i = i + 1
  105.             elif type(av) in (type(()), type([])):
  106.                 for a in av:
  107.                     if isinstance(a, SubPattern):
  108.                         if not nl: print
  109.                         a.dump(level+1); nl = 1
  110.                     else:
  111.                         print a, ; nl = 0
  112.             else:
  113.                 print av, ; nl = 0
  114.             if not nl: print
  115.     def __repr__(self):
  116.         return repr(self.data)
  117.     def __len__(self):
  118.         return len(self.data)
  119.     def __delitem__(self, index):
  120.         del self.data[index]
  121.     def __getitem__(self, index):
  122.         return self.data[index]
  123.     def __setitem__(self, index, code):
  124.         self.data[index] = code
  125.     def __getslice__(self, start, stop):
  126.         return SubPattern(self.pattern, self.data[start:stop])
  127.     def insert(self, index, code):
  128.         self.data.insert(index, code)
  129.     def append(self, code):
  130.         self.data.append(code)
  131.     def getwidth(self):
  132.         # determine the width (min, max) for this subpattern
  133.         if self.width:
  134.             return self.width
  135.         lo = hi = 0L
  136.         for op, av in self.data:
  137.             if op is BRANCH:
  138.                 i = sys.maxint
  139.                 j = 0
  140.                 for av in av[1]:
  141.                     l, h = av.getwidth()
  142.                     i = min(i, l)
  143.                     j = max(j, h)
  144.                 lo = lo + i
  145.                 hi = hi + j
  146.             elif op is CALL:
  147.                 i, j = av.getwidth()
  148.                 lo = lo + i
  149.                 hi = hi + j
  150.             elif op is SUBPATTERN:
  151.                 i, j = av[1].getwidth()
  152.                 lo = lo + i
  153.                 hi = hi + j
  154.             elif op in (MIN_REPEAT, MAX_REPEAT):
  155.                 i, j = av[2].getwidth()
  156.                 lo = lo + long(i) * av[0]
  157.                 hi = hi + long(j) * av[1]
  158.             elif op in (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY):
  159.                 lo = lo + 1
  160.                 hi = hi + 1
  161.             elif op == SUCCESS:
  162.                 break
  163.         self.width = int(min(lo, sys.maxint)), int(min(hi, sys.maxint))
  164.         return self.width
  165.  
  166. class Tokenizer:
  167.     def __init__(self, string):
  168.         self.string = string
  169.         self.index = 0
  170.         self.__next()
  171.     def __next(self):
  172.         if self.index >= len(self.string):
  173.             self.next = None
  174.             return
  175.         char = self.string[self.index]
  176.         if char[0] == "\\":
  177.             try:
  178.                 c = self.string[self.index + 1]
  179.             except IndexError:
  180.                 raise error, "bogus escape"
  181.             char = char + c
  182.         self.index = self.index + len(char)
  183.         self.next = char
  184.     def match(self, char):
  185.         if char == self.next:
  186.             self.__next()
  187.             return 1
  188.         return 0
  189.     def get(self):
  190.         this = self.next
  191.         self.__next()
  192.         return this
  193.     def tell(self):
  194.         return self.index, self.next
  195.     def seek(self, index):
  196.         self.index, self.next = index
  197.  
  198. def isident(char):
  199.     return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_"
  200.  
  201. def isdigit(char):
  202.     return "0" <= char <= "9"
  203.  
  204. def isname(name):
  205.     # check that group name is a valid string
  206.     if not isident(name[0]):
  207.         return 0
  208.     for char in name:
  209.         if not isident(char) and not isdigit(char):
  210.             return 0
  211.     return 1
  212.  
  213. def _group(escape, groups):
  214.     # check if the escape string represents a valid group
  215.     try:
  216.         gid = int(escape[1:])
  217.         if gid and gid < groups:
  218.             return gid
  219.     except ValueError:
  220.         pass
  221.     return None # not a valid group
  222.  
  223. def _class_escape(source, escape):
  224.     # handle escape code inside character class
  225.     code = ESCAPES.get(escape)
  226.     if code:
  227.         return code
  228.     code = CATEGORIES.get(escape)
  229.     if code:
  230.         return code
  231.     try:
  232.         if escape[1:2] == "x":
  233.             # FIXME: in 2.0, \xNN must have exactly two digits
  234.             while source.next in HEXDIGITS:
  235.                 escape = escape + source.get()
  236.             escape = escape[2:]
  237.             return LITERAL, int(escape[-4:], 16) & CHARMASK
  238.         elif str(escape[1:2]) in OCTDIGITS:
  239.             while source.next in OCTDIGITS:
  240.                 escape = escape + source.get()
  241.             escape = escape[1:]
  242.             return LITERAL, int(escape[-6:], 8) & CHARMASK
  243.         if len(escape) == 2:
  244.             return LITERAL, ord(escape[1])
  245.     except ValueError:
  246.         pass
  247.     raise error, "bogus escape: %s" % repr(escape)
  248.  
  249. def _escape(source, escape, state):
  250.     # handle escape code in expression
  251.     code = CATEGORIES.get(escape)
  252.     if code:
  253.         return code
  254.     code = ESCAPES.get(escape)
  255.     if code:
  256.         return code
  257.     try:
  258.         if escape[1:2] == "x":
  259.             while source.next in HEXDIGITS:
  260.                 escape = escape + source.get()
  261.             escape = escape[2:]
  262.             return LITERAL, int(escape[-4:], 16) & CHARMASK
  263.         elif escape[1:2] in DIGITS:
  264.             while 1:
  265.                 group = _group(escape, state.groups)
  266.                 if group:
  267.                     if (not source.next or
  268.                         not _group(escape + source.next, state.groups)):
  269.                         return GROUPREF, group
  270.                     escape = escape + source.get()
  271.                 elif source.next in OCTDIGITS:
  272.                     escape = escape + source.get()
  273.                 else:
  274.                     break
  275.             escape = escape[1:]
  276.             return LITERAL, int(escape[-6:], 8) & CHARMASK
  277.         if len(escape) == 2:
  278.             return LITERAL, ord(escape[1])
  279.     except ValueError:
  280.         pass
  281.     raise error, "bogus escape: %s" % repr(escape)
  282.  
  283. def _parse_sub(source, state, nested=1):
  284.     # parse an alternation: a|b|c
  285.  
  286.     items = []
  287.     while 1:
  288.         items.append(_parse(source, state))
  289.         if source.match("|"):
  290.             continue
  291.         if not nested:
  292.             break
  293.         if not source.next or source.match(")"):
  294.             break
  295.         else:
  296.             raise error, "pattern not properly closed"
  297.  
  298.     if len(items) == 1:
  299.         return items[0]
  300.  
  301.     subpattern = SubPattern(state)
  302.  
  303.     # check if all items share a common prefix
  304.     while 1:
  305.         prefix = None
  306.         for item in items:
  307.             if not item:
  308.                 break
  309.             if prefix is None:
  310.                 prefix = item[0]
  311.             elif item[0] != prefix:
  312.                 break
  313.         else:
  314.             # all subitems start with a common "prefix".
  315.             # move it out of the branch
  316.             for item in items:
  317.                 del item[0]
  318.             subpattern.append(prefix)
  319.             continue # check next one
  320.         break
  321.  
  322.     # check if the branch can be replaced by a character set
  323.     for item in items:
  324.         if len(item) != 1 or item[0][0] != LITERAL:
  325.             break
  326.     else:
  327.         # we can store this as a character set instead of a
  328.         # branch (the compiler may optimize this even more)
  329.         set = []
  330.         for item in items:
  331.             set.append(item[0])
  332.         subpattern.append((IN, set))
  333.         return subpattern
  334.  
  335.     subpattern.append((BRANCH, (None, items)))
  336.     return subpattern
  337.  
  338. def _parse(source, state):
  339.     # parse a simple pattern
  340.  
  341.     subpattern = SubPattern(state)
  342.  
  343.     while 1:
  344.  
  345.         if source.next in ("|", ")"):
  346.             break # end of subpattern
  347.         this = source.get()
  348.         if this is None:
  349.             break # end of pattern
  350.  
  351.         if state.flags & SRE_FLAG_VERBOSE:
  352.             # skip whitespace and comments
  353.             if this in WHITESPACE:
  354.                 continue
  355.             if this == "#":
  356.                 while 1:
  357.                     this = source.get()
  358.                     if this in (None, "\n"):
  359.                         break
  360.                 continue
  361.  
  362.         if this and this[0] not in SPECIAL_CHARS:
  363.             subpattern.append((LITERAL, ord(this)))
  364.  
  365.         elif this == "[":
  366.             # character set
  367.             set = []
  368. ##          if source.match(":"):
  369. ##              pass # handle character classes
  370.             if source.match("^"):
  371.                 set.append((NEGATE, None))
  372.             # check remaining characters
  373.             start = set[:]
  374.             while 1:
  375.                 this = source.get()
  376.                 if this == "]" and set != start:
  377.                     break
  378.                 elif this and this[0] == "\\":
  379.                     code1 = _class_escape(source, this)
  380.                 elif this:
  381.                     code1 = LITERAL, ord(this)
  382.                 else:
  383.                     raise error, "unexpected end of regular expression"
  384.                 if source.match("-"):
  385.                     # potential range
  386.                     this = source.get()
  387.                     if this == "]":
  388.                         set.append(code1)
  389.                         set.append((LITERAL, ord("-")))
  390.                         break
  391.                     else:
  392.                         if this[0] == "\\":
  393.                             code2 = _class_escape(source, this)
  394.                         else:
  395.                             code2 = LITERAL, ord(this)
  396.                         if code1[0] != LITERAL or code2[0] != LITERAL:
  397.                             raise error, "illegal range"
  398.                         set.append((RANGE, (code1[1], code2[1])))
  399.                 else:
  400.                     if code1[0] is IN:
  401.                         code1 = code1[1][0]
  402.                     set.append(code1)
  403.  
  404.             # FIXME: <fl> move set optimization to compiler!
  405.             if len(set)==1 and set[0][0] is LITERAL:
  406.                 subpattern.append(set[0]) # optimization
  407.             elif len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:
  408.                 subpattern.append((NOT_LITERAL, set[1][1])) # optimization
  409.             else:
  410.                 # FIXME: <fl> add charmap optimization
  411.                 subpattern.append((IN, set))
  412.  
  413.         elif this and this[0] in REPEAT_CHARS:
  414.             # repeat previous item
  415.             if this == "?":
  416.                 min, max = 0, 1
  417.             elif this == "*":
  418.                 min, max = 0, MAXREPEAT
  419.             elif this == "+":
  420.                 min, max = 1, MAXREPEAT
  421.             elif this == "{":
  422.                 here = source.tell()
  423.                 min, max = 0, MAXREPEAT
  424.                 lo = hi = ""
  425.                 while source.next in DIGITS:
  426.                     lo = lo + source.get()
  427.                 if source.match(","):
  428.                     while source.next in DIGITS:
  429.                         hi = hi + source.get()
  430.                 else:
  431.                     hi = lo
  432.                 if not source.match("}"):
  433.                     subpattern.append((LITERAL, ord(this)))
  434.                     source.seek(here)
  435.                     continue
  436.                 if lo:
  437.                     min = int(lo)
  438.                 if hi:
  439.                     max = int(hi)
  440.                 # FIXME: <fl> check that hi >= lo!
  441.             else:
  442.                 raise error, "not supported"
  443.             # figure out which item to repeat
  444.             if subpattern:
  445.                 item = subpattern[-1:]
  446.             else:
  447.                 raise error, "nothing to repeat"
  448.             if source.match("?"):
  449.                 subpattern[-1] = (MIN_REPEAT, (min, max, item))
  450.             else:
  451.                 subpattern[-1] = (MAX_REPEAT, (min, max, item))
  452.  
  453.         elif this == ".":
  454.             subpattern.append((ANY, None))
  455.  
  456.         elif this == "(":
  457.             group = 1
  458.             name = None
  459.             if source.match("?"):
  460.                 group = 0
  461.                 # options
  462.                 if source.match("P"):
  463.                     # python extensions
  464.                     if source.match("<"):
  465.                         # named group: skip forward to end of name
  466.                         name = ""
  467.                         while 1:
  468.                             char = source.get()
  469.                             if char is None:
  470.                                 raise error, "unterminated name"
  471.                             if char == ">":
  472.                                 break
  473.                             name = name + char
  474.                         group = 1
  475.                         if not isname(name):
  476.                             raise error, "illegal character in group name"
  477.                     elif source.match("="):
  478.                         # named backreference
  479.                         name = ""
  480.                         while 1:
  481.                             char = source.get()
  482.                             if char is None:
  483.                                 raise error, "unterminated name"
  484.                             if char == ")":
  485.                                 break
  486.                             name = name + char
  487.                         if not isname(name):
  488.                             raise error, "illegal character in group name"
  489.                         gid = state.groupdict.get(name)
  490.                         if gid is None:
  491.                             raise error, "unknown group name"
  492.                         subpattern.append((GROUPREF, gid))
  493.                         continue
  494.                     else:
  495.                         char = source.get()
  496.                         if char is None:
  497.                             raise error, "unexpected end of pattern"
  498.                         raise error, "unknown specifier: ?P%s" % char
  499.                 elif source.match(":"):
  500.                     # non-capturing group
  501.                     group = 2
  502.                 elif source.match("#"):
  503.                     # comment
  504.                     while 1:
  505.                         if source.next is None or source.next == ")":
  506.                             break
  507.                         source.get()
  508.                 elif source.next in ("=", "!", "<"):
  509.                     # lookahead assertions
  510.                     char = source.get()
  511.                     dir = 1
  512.                     if char == "<":
  513.                         if source.next not in ("=", "!"):
  514.                             raise error, "syntax error"
  515.                         dir = -1 # lookbehind
  516.                         char = source.get()
  517.                     p = _parse_sub(source, state)
  518.                     if char == "=":
  519.                         subpattern.append((ASSERT, (dir, p)))
  520.                     else:
  521.                         subpattern.append((ASSERT_NOT, (dir, p)))
  522.                     continue
  523.                 else:
  524.                     # flags
  525.                     while FLAGS.has_key(source.next):
  526.                         state.flags = state.flags | FLAGS[source.get()]
  527.             if group:
  528.                 # parse group contents
  529.                 if group == 2:
  530.                     # anonymous group
  531.                     group = None
  532.                 else:
  533.                     group = state.getgroup(name)
  534.                 p = _parse_sub(source, state)
  535.                 subpattern.append((SUBPATTERN, (group, p)))
  536.             else:
  537.                 while 1:
  538.                     char = source.get()
  539.                     if char is None or char == ")":
  540.                         break
  541.                     raise error, "unknown extension"
  542.  
  543.         elif this == "^":
  544.             subpattern.append((AT, AT_BEGINNING))
  545.  
  546.         elif this == "$":
  547.             subpattern.append((AT, AT_END))
  548.  
  549.         elif this and this[0] == "\\":
  550.             code = _escape(source, this, state)
  551.             subpattern.append(code)
  552.  
  553.         else:
  554.             raise error, "parser error"
  555.  
  556.     return subpattern
  557.  
  558. def parse(str, flags=0, pattern=None):
  559.     # parse 're' pattern into list of (opcode, argument) tuples
  560.  
  561.     source = Tokenizer(str)
  562.  
  563.     if pattern is None:
  564.         pattern = Pattern()
  565.     pattern.flags = flags
  566.  
  567.     p = _parse_sub(source, pattern, 0)
  568.  
  569.     tail = source.get()
  570.     if tail == ")":
  571.         raise error, "unbalanced parenthesis"
  572.     elif tail:
  573.         raise error, "bogus characters at end of regular expression"
  574.  
  575.     # p.dump()
  576.  
  577.     return p
  578.  
  579. def parse_template(source, pattern):
  580.     # parse 're' replacement string into list of literals and
  581.     # group references
  582.     s = Tokenizer(source)
  583.     p = []
  584.     a = p.append
  585.     while 1:
  586.         this = s.get()
  587.         if this is None:
  588.             break # end of replacement string
  589.         if this and this[0] == "\\":
  590.             # group
  591.             if this == "\\g":
  592.                 name = ""
  593.                 if s.match("<"):
  594.                     while 1:
  595.                         char = s.get()
  596.                         if char is None:
  597.                             raise error, "unterminated group name"
  598.                         if char == ">":
  599.                             break
  600.                         name = name + char
  601.                 if not name:
  602.                     raise error, "bad group name"
  603.                 try:
  604.                     index = int(name)
  605.                 except ValueError:
  606.                     if not isname(name):
  607.                         raise error, "illegal character in group name"
  608.                     try:
  609.                         index = pattern.groupindex[name]
  610.                     except KeyError:
  611.                         raise IndexError, "unknown group name"
  612.                 a((MARK, index))
  613.             elif len(this) > 1 and this[1] in DIGITS:
  614.                 code = None
  615.                 while 1:
  616.                     group = _group(this, pattern.groups+1)
  617.                     if group:
  618.                         if (not s.next or
  619.                             not _group(this + s.next, pattern.groups+1)):
  620.                             code = MARK, int(group)
  621.                             break
  622.                     elif s.next in OCTDIGITS:
  623.                         this = this + s.get()
  624.                     else:
  625.                         break
  626.                 if not code:
  627.                     this = this[1:]
  628.                     code = LITERAL, int(this[-6:], 8) & CHARMASK
  629.                 a(code)
  630.             else:
  631.                 try:
  632.                     a(ESCAPES[this])
  633.                 except KeyError:
  634.                     for c in this:
  635.                         a((LITERAL, ord(c)))
  636.         else:
  637.             a((LITERAL, ord(this)))
  638.     return p
  639.  
  640. def expand_template(template, match):
  641.     # FIXME: <fl> this is sooooo slow.  drop in the slicelist
  642.     # code instead
  643.     p = []
  644.     a = p.append
  645.     sep = match.string[:0]
  646.     if type(sep) is type(""):
  647.         char = chr
  648.     else:
  649.         char = unichr
  650.     for c, s in template:
  651.         if c is LITERAL:
  652.             a(char(s))
  653.         elif c is MARK:
  654.             s = match.group(s)
  655.             if s is None:
  656.                 raise error, "empty group"
  657.             a(s)
  658.     return string.join(p, sep)
  659.